{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "XdfxlczNtXK-"
   },
   "source": [
    "# A practical introduction to Reinforcement Learning\n",
    "\n",
    "Most of you have probably heard of AI learning to play computer games on their own, a very popular example being Deepmind. Deepmind hit the news when their AlphaGo program defeated the South Korean Go world champion in 2016. There had been many successful attempts in the past to develop agents with the intent of playing Atari games like Breakout, Pong, and Space Invaders.\n",
    "\n",
    "You know what's common in most of these programs? A paradigm of Machine Learning known as **Reinforcement Learning**. For those of you that are new to RL, let's get some understand with few analogies.\n",
    "\n",
    "## Reinforcement Learning Analogy\n",
    "Consider the scenario of teaching a dog new tricks. The dog doesn't understand our language, so we can't tell him what to do. Instead, we follow a different strategy. We emulate a situation (or a cue), and the dog tries to respond in many different ways. If the dog's response is the desired one, we reward them with snacks. Now guess what, the next time the dog is exposed to the same situation, the dog executes a similar action with even more enthusiasm in expectation of more food. That's like learning \"what to do\" from positive experiences. Similarly, dogs will tend to learn what not to do when face with negative experiences. \n",
    "\n",
    "That's exactly how Reinforcement Learning works in a broader sense:\n",
    "- Your dog is an \"agent\" that is exposed to the **environment**. The environment could in your house, with you.\n",
    "- The situations they encounter are analogous to a **state**. An example of a state could be your dog standing and you use a specific word in a certain tone in your living room\n",
    "- Our agents react by performing an **action** to transition from one \"state\" to another \"state,\" your dog goes from standing to sitting, for example.\n",
    "- After the transition, they may receive a **reward** or **penalty** in return. You give them a treat! Or a \"No\" as a penalty.\n",
    "- The **policy** is the strategy of choosing an action given a state in expectation of better outcomes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Fq-CR1CUtXLC"
   },
   "source": [
    "Reinforcement Learning lies between the spectrum of Supervised Learning and Unsupervised Learning, and there's a few important things to note:\n",
    "\n",
    "    1. Being greedy doesn't always work \n",
    "\n",
    "There are things that are easy to do for instant gratification, and there's things that provide long term rewards\n",
    "The goal is to not be greedy by looking for the quick immediate rewards, but instead to optimize for maximum rewards over the whole training.\n",
    "\n",
    "    2. Sequence matters in Reinforcement Learning\n",
    "\n",
    "The reward agent does not just depend on the current state, but the entire history of states. Unlike supervised and unsupervised learning, time is important here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Fq-CR1CUtXLC"
   },
   "source": [
    "### The Reinforcement Process\n",
    "\n",
    "In a way, Reinforcement Learning is the science of making optimal decisions using experiences. \n",
    "Breaking it down, the process of Reinforcement Learning involves these simple steps:\n",
    "\n",
    "1. Observation of the environment\n",
    "2. Deciding how to act using some strategy\n",
    "3. Acting accordingly\n",
    "4. Receiving a reward or penalty\n",
    "5. Learning from the experiences and refining our strategy\n",
    "6. Iterate until an optimal strategy is found\n",
    "\n",
    "Let's now understand Reinforcement Learning by actually developing an agent to learn to play a game automatically on its own."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Fq-CR1CUtXLC"
   },
   "source": [
    "## Example Design: Self-Driving Cab\n",
    "\n",
    "Let's design a simulation of a self-driving cab. The major goal is to demonstrate, in a simplified environment, how you can use RL techniques to develop an efficient and safe approach for tackling this problem.\n",
    "\n",
    "The Smartcab's job is to pick up the passenger at one location and drop them off in another. Here are a few things that we'd love our Smartcab to take care of:\n",
    "\n",
    "- Drop off the passenger to the right location.\n",
    "- Save passenger's time by taking minimum time possible to drop off\n",
    "- Take care of passenger's safety and traffic rules\n",
    "\n",
    "There are different aspects that need to be considered here while modeling an RL solution to this problem: rewards, states, and actions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Fq-CR1CUtXLC"
   },
   "source": [
    "### 1. Rewards\n",
    "\n",
    "Since the agent (the imaginary driver) is reward-motivated and is going to learn how to control the cab by trial experiences in the environment, we need to decide the **rewards** and/or **penalties** and their magnitude accordingly. Here a few points to consider:\n",
    "\n",
    "- The agent should receive a high positive reward for a successful dropoff because this behavior is highly desired\n",
    "- The agent should be penalized if it tries to drop off a passenger in wrong locations\n",
    "- The agent should get a slight negative reward for not making it to the destination after every time-step. \"Slight\" negative because we would prefer our agent to reach late instead of making wrong moves trying to reach to the destination as fast as possible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Fq-CR1CUtXLC"
   },
   "source": [
    "### 2. State Space\n",
    "\n",
    "In Reinforcement Learning, the agent encounters a state, and then takes action according to the state it's in. \n",
    "\n",
    "The **State Space** is the set of all possible situations our taxi could inhabit. The state should contain useful information the agent needs to make the right action. \n",
    "\n",
    "Let's say we have a training area for our Smartcab where we are teaching it to transport people in a parking lot to four different locations (R, G, Y, B): \n",
    "\n",
    "<img src=\"assets/Reinforcement Learning Taxi Env.png\">\n",
    "\n",
    "Let's assume Smartcab is the only vehicle in this parking lot. We can break up the parking lot into a 5x5 grid, which gives us 25 possible taxi locations. These 25 locations are one part of our state space. Notice the current location state of our taxi is coordinate (3, 1).\n",
    "\n",
    "You'll also notice there are four (4) locations that we can pick up and drop off a passenger: R, G, Y, B or `[(0,0), (0,4), (4,0), (4,3)] ` in (row, col) coordinates. Our illustrated passenger is in location **Y** and they wish to go to location **R**.\n",
    "\n",
    "When we also account for one (1) additional passenger state of being inside the taxi, we can take all combinations of passenger locations and destination locations to come to a total number of states for our taxi environment; there's four (4) destinations and five (4 + 1)  passenger locations.\n",
    "\n",
    "So, our taxi environment has $5 \\times 5 \\times 5 \\times 4 = 500$ total possible states."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Fq-CR1CUtXLC"
   },
   "source": [
    "### 3. Action Space\n",
    "\n",
    "The agent encounters one of the 500 states and it takes an action. The action in our case can be to move in a direction or decide to pickup/dropoff a passenger. \n",
    "\n",
    "In other words, we have six possible actions:\n",
    "\n",
    "1. `south`\n",
    "2. `north`\n",
    "3. `east`\n",
    "4. `west`\n",
    "5. `pickup`\n",
    "6. `dropoff`\n",
    "\n",
    "This is the **action space**: the set of all the actions that our agent can take in a given state.\n",
    "\n",
    "You'll notice in the illustration above, that the taxi cannot perform certain actions in certain states due to walls. In environment's code, we will simply provide a -1 penalty for every wall hit and the taxi won't move anywhere. This will just rack up penalties causing the taxi to consider going around the wall."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "-Xv15QDTtXLC"
   },
   "source": [
    "## Implementation with Python\n",
    "\n",
    "Fortunately, [OpenAI Gym](https://gym.openai.com/) has this exact environment already built for us.\n",
    "\n",
    "Gym provides different game environments which we can plug into our code and test an agent. The library takes care of API for providing all the information that our agent would require, like possible actions, score, and current state. We just need to focus just on the algorithm part for our agent.\n",
    "\n",
    "We'll be using the Gym environment called `Taxi-V2`, which all of the details explained above were pulled from. The objectives, rewards, and actions are all the same.\n",
    "\n",
    "### Gym's interface\n",
    "\n",
    "We need to install `gym` first. Executing the following in a Jupyter notebook should work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install cmake 'gym[atari]' scipy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "u4LUXTY2tXLI"
   },
   "source": [
    "Once installed, we can load the game environment and render what it looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "base_uri": "https://localhost:8080/",
     "height": 151
    },
    "colab_type": "code",
    "executionInfo": {
     "elapsed": 262,
     "status": "ok",
     "timestamp": 1526761210212,
     "user": {
      "displayName": "Brendan Martin",
      "photoUrl": "//lh5.googleusercontent.com/-Z3stmcnT9QY/AAAAAAAAAAI/AAAAAAAABHo/Fxg5ytfMCG0/s50-c-k-no/photo.jpg",
      "userId": "116172645966902242675"
     },
     "user_tz": 240
    },
    "id": "PrkqSSPKtXLJ",
    "outputId": "0316d676-2479-4e09-8f9d-c4a141f270ee"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+---------+\n",
      "|\u001b[34;1mR\u001b[0m: | : :G|\n",
      "| : : : : |\n",
      "| : : : : |\n",
      "| |\u001b[43m \u001b[0m: | : |\n",
      "|Y| : |\u001b[35mB\u001b[0m: |\n",
      "+---------+\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import gym\n",
    "\n",
    "env = gym.make(\"Taxi-v2\").env\n",
    "\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4mhzfqiptXLM"
   },
   "source": [
    "The core gym interface is `env`, which is the unified environment interface. The following are the `env` methods that would be quite helpful to us:\n",
    "\n",
    "- `env.reset`: Resets the environment and returns a random initial state.\n",
    "- `env.step(action)`: Step the environment by one timestep. Returns\n",
    "    + **observation**: Observations of the environment\n",
    "    + **reward**: If your action was beneficial or not\n",
    "    + **done**: Indicates if we have successfully picked up and dropped off a passenger, also called one *episode*\n",
    "    + **info**: Additional info such as performance and latency for debugging purposes\n",
    "- `env.render`: Renders one frame of the environment (helpful in visualizing the environment)\n",
    "\n",
    "Note: We are using the `.env` on the end of `make` to avoid training stopping at 200 iterations, which is the default for the new version of Gym ([reference](https://stackoverflow.com/a/42802225)). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4mhzfqiptXLM"
   },
   "source": [
    "###  Reminder of our problem\n",
    "\n",
    "Here's our restructured problem statement (from Gym docs):\n",
    "\n",
    "> There are 4 locations (labeled by different letters), and our job is to pick up the passenger at one location and drop him off at another. We receive +20 points for a successful drop-off and lose 1 point for every time-step it takes. There is also a 10 point penalty for illegal pick-up and drop-off actions.\n",
    "\n",
    "Let's dive more into the environment."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "base_uri": "https://localhost:8080/",
     "height": 185
    },
    "colab_type": "code",
    "executionInfo": {
     "elapsed": 298,
     "status": "ok",
     "timestamp": 1526761215189,
     "user": {
      "displayName": "Brendan Martin",
      "photoUrl": "//lh5.googleusercontent.com/-Z3stmcnT9QY/AAAAAAAAAAI/AAAAAAAABHo/Fxg5ytfMCG0/s50-c-k-no/photo.jpg",
      "userId": "116172645966902242675"
     },
     "user_tz": 240
    },
    "id": "ts6O2VUftXLM",
    "outputId": "4758bfd7-b0b8-4989-810f-586f3c729b28"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+---------+\n",
      "|\u001b[35mR\u001b[0m: | : :G|\n",
      "| : : : : |\n",
      "| : : : : |\n",
      "| |\u001b[43m \u001b[0m: | : |\n",
      "|Y| : |\u001b[34;1mB\u001b[0m: |\n",
      "+---------+\n",
      "\n",
      "Action Space Discrete(6)\n",
      "State Space Discrete(500)\n"
     ]
    }
   ],
   "source": [
    "env.reset() # reset environment to a new, random state\n",
    "env.render()\n",
    "\n",
    "print(\"Action Space {}\".format(env.action_space))\n",
    "print(\"State Space {}\".format(env.observation_space))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "7y2IDKy9tXLU"
   },
   "source": [
    "- The **filled square** represents the taxi, which is yellow without a passenger and green with a passenger. \n",
    "- The **pipe (\"|\")** represents a wall which the taxi cannot cross. \n",
    "- **R, G, Y, B** are the possible pickup and destination locations. The **blue letter** represents the current passenger pick-up location, and the **purple letter** is the current destination. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "7y2IDKy9tXLU"
   },
   "source": [
    "As verified by the prints, we have an **Action Space** of size 6 and a **State Space** of size 500. As you'll see, our RL algorithm won't need any more information than these two things. All we need is a way to identify a state uniquely by assigning a unique number to every possible state, and RL learns to choose an action number from 0-5 where:\n",
    "\n",
    "- 0 = south\n",
    "- 1 = north\n",
    "- 2 = east\n",
    "- 3 = west\n",
    "- 4 = pickup\n",
    "- 5 = dropoff\n",
    "\n",
    "Recall that the 500 states correspond to a encoding of the taxi's location, the passenger's location, and the destination location. \n",
    "\n",
    "Reinforcement Learning will learn a mapping of **states** to the optimal **action** to perform in that state by *exploration*, i.e. the agent explores the environment and takes actions based off rewards defined in the environment.\n",
    "\n",
    "The optimal action for each state is the action that has the **highest cumulative long-term reward**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "7y2IDKy9tXLU"
   },
   "source": [
    "#### Back to our illustration\n",
    "We can actually take our illustration above, encode its state, and give it to the environment to render in Gym. Recall that we have the taxi at row 3, column 1, our passenger is at location 2, and our destination is location 0. Using the Taxi-v2 state encoding method, we can do the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "State: 328\n",
      "+---------+\n",
      "|\u001b[35mR\u001b[0m: | : :G|\n",
      "| : : : : |\n",
      "| : : : : |\n",
      "| |\u001b[43m \u001b[0m: | : |\n",
      "|\u001b[34;1mY\u001b[0m| : |B: |\n",
      "+---------+\n",
      "\n"
     ]
    }
   ],
   "source": [
    "state = env.encode(3, 1, 2, 0) # (taxi row, taxi column, passenger index, destination index)\n",
    "print(\"State:\", state)\n",
    "\n",
    "env.s = state\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are using our illustration's coordinates to generate a number corresponding to a state between 0 and 499, which turns out to be **328** for our illustration's state.\n",
    "\n",
    "Then we can set the environment's state manually with `env.env.s` using that encoded number. You can play around with the numbers and you'll see the taxi, passenger, and destination move around."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### The Reward Table\n",
    "When the Taxi environment is created, there is an initial Reward table that's also created, called `P`. We can think of it like a matrix that has the number of states as rows and number of actions as columns, i.e. a $states \\ \\times \\ actions$ matrix.\n",
    "\n",
    "Since every state is in this matrix, we can see the default reward values assigned to our illustration's state:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: [(1.0, 428, -1, False)],\n",
       " 1: [(1.0, 228, -1, False)],\n",
       " 2: [(1.0, 348, -1, False)],\n",
       " 3: [(1.0, 328, -1, False)],\n",
       " 4: [(1.0, 328, -10, False)],\n",
       " 5: [(1.0, 328, -10, False)]}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "env.P[328]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This dictionary has the structure `{action: [(probability, nextstate, reward, done)]}`.\n",
    "\n",
    "A few things to note:\n",
    "- The 0-5 corresponds to the actions (south, north, east, west, pickup, dropoff) the taxi can perform at our current state in the illustration. \n",
    "- In this env, `probability` is always 1.0. \n",
    "- The `nextstate` is the state we would be in if we take the action at this index of the dict\n",
    "- All the movement actions have a -1 reward and the pickup/dropoff actions have -10 reward in this particular state. If we are in a state where the taxi has a passenger and is on top of the right destination, we would see a reward of 20 at the dropoff action (5)\n",
    "- `done` is used to tell us when we have successfully dropped off a passenger in the right location. Each successfull dropoff is the end of an **episode**\n",
    "\n",
    "Note that if our agent chose to explore action two (2) in this state it would be going East into a wall. The source code has made it impossible to actually move the taxi across a wall, so if the taxi chooses that action, it will just keep acruing -1 penalties, which affects the **long-term reward**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "7y2IDKy9tXLU"
   },
   "source": [
    "### Solving the environment without Reinforcement Learning\n",
    "\n",
    "Let's see what would happen if we try to brute-force our way to solving the problem without RL.\n",
    "\n",
    "Since we have our `P` table for default rewards in each state, we can try to have our taxi navigate just using that.\n",
    "\n",
    "We'll create an infinite loop which runs until one passenger reaches one destination (one **episode**), or in other words, when the received reward is 20. The `env.action_space.sample()` method automatically selects one random action from set of all possible actions.\n",
    "\n",
    "Let's see what happens:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "JieQPZ1NtXLU"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Timesteps taken: 1665\n",
      "Penalties incurred: 526\n"
     ]
    }
   ],
   "source": [
    "env.s = 328  # set environment to illustration's state\n",
    "\n",
    "epochs = 0\n",
    "penalties, reward = 0, 0\n",
    "\n",
    "frames = [] # for animation\n",
    "\n",
    "done = False\n",
    "\n",
    "while not done:\n",
    "    action = env.action_space.sample()\n",
    "    state, reward, done, info = env.step(action)\n",
    "\n",
    "    if reward == -10:\n",
    "        penalties += 1\n",
    "    \n",
    "    # Put each rendered frame into dict for animation\n",
    "    frames.append({\n",
    "        'frame': env.render(mode='ansi'),\n",
    "        'state': state,\n",
    "        'action': action,\n",
    "        'reward': reward\n",
    "        }\n",
    "    )\n",
    "\n",
    "    epochs += 1\n",
    "    \n",
    "    \n",
    "print(\"Timesteps taken: {}\".format(epochs))\n",
    "print(\"Penalties incurred: {}\".format(penalties))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     },
     "base_uri": "https://localhost:8080/",
     "height": 531
    },
    "colab_type": "code",
    "executionInfo": {
     "elapsed": 181,
     "status": "error",
     "timestamp": 1526761248344,
     "user": {
      "displayName": "Brendan Martin",
      "photoUrl": "//lh5.googleusercontent.com/-Z3stmcnT9QY/AAAAAAAAAAI/AAAAAAAABHo/Fxg5ytfMCG0/s50-c-k-no/photo.jpg",
      "userId": "116172645966902242675"
     },
     "user_tz": 240
    },
    "id": "teQv1HPRtXLX",
    "outputId": "8053f405-c9da-4ab1-8e48-85596fc23738",
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "+---------+\n",
      "|\u001b[35m\u001b[42mR\u001b[0m\u001b[0m: | : :G|\n",
      "| : : : : |\n",
      "| : : : : |\n",
      "| | : | : |\n",
      "|Y| : |B: |\n",
      "+---------+\n",
      "  (Dropoff)\n",
      "\n",
      "Timestep: 1665\n",
      "State: 16\n",
      "Action: 5\n",
      "Reward: 20\n"
     ]
    }
   ],
   "source": [
    "from IPython.display import clear_output\n",
    "from time import sleep\n",
    "\n",
    "def print_frames(frames):\n",
    "    for i, frame in enumerate(frames):\n",
    "        clear_output(wait=True)\n",
    "        print(frame['frame'].getvalue())\n",
    "        print(f\"Timestep: {i + 1}\")\n",
    "        print(f\"State: {frame['state']}\")\n",
    "        print(f\"Action: {frame['action']}\")\n",
    "        print(f\"Reward: {frame['reward']}\")\n",
    "        sleep(.1)\n",
    "        \n",
    "print_frames(frames)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "L6AfP_YjtXLa"
   },
   "source": [
    "Not good. Our agent takes thousands of timesteps and makes lots of wrong drop offs to deliver just one passenger to the right destination.\n",
    "\n",
    "This is because we aren't *learning* from past experience. We can run this over and over, and it will never optimize. The agent has no memory of which action was best for each state, which is exactly what Reinforcement Learning will do for us."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qC-pX8P-tXLb"
   },
   "source": [
    "### Enter Reinforcement Learning\n",
    "\n",
    "We are going to use a simple RL algorithm called *Q-learning* which will give our agent some memory.\n",
    "\n",
    "#### Intro to Q-learning \n",
    "\n",
    "Essentially, Q-learning lets the agent use the environment's rewards to learn, over time, the best action to take in a given state. \n",
    "\n",
    "In our Taxi environment, we have the reward table, `P`, that the agent will learn from. It does thing by looking receiving a reward for taking an action in the current state, then updating a *Q-value* to remember if that action was beneficial.\n",
    "\n",
    "The values store in the Q-table are called a *Q-values*, and they map to a `(state, action)` combination.\n",
    "\n",
    "A Q-value for a particular state-action combination is representative of the \"quality\" of an action taken from that state. Better Q-values imply better chances of getting greater rewards. \n",
    "\n",
    "For example, if the taxi is faced with a state that includes a passenger at its current location, it is highly likely that the Q-value for `pickup` is higher when compared to other actions, like `dropoff` or `north`.\n",
    "\n",
    "Q-values are initialized to an arbitrary value, and as the agent exposes itself to the environment and receives different rewards by executing different actions, the Q-values are updated using the equation:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\\Large Q({\\small state}, {\\small action}) \\leftarrow (1 - \\alpha) Q({\\small state}, {\\small action}) + \\alpha \\Big({\\small reward} + \\gamma \\max_{a} Q({\\small next \\ state}, {\\small all \\ actions})\\Big)$$\n",
    "\n",
    "Where:\n",
    "- $\\Large \\alpha$ (alpha) is the learning rate ($0 < \\alpha \\leq 1$) - Just like in supervised learning settings, $\\alpha$ is the extent to which our Q-values are being updated in every iteration.\n",
    "- $\\Large \\gamma$ (gamma) is the discount factor ($0 \\leq \\gamma \\leq 1$) - determines how much importance we want to give to future rewards. A high value for the discount factor (close to **1**) captures the long-term effective award, whereas, a discount factor of **0** makes our agent consider only immediate reward, hence making it greedy.\n",
    "\n",
    "**What is this saying?**\n",
    "We are assigning ($\\leftarrow$), or updating, the Q-value of the agent's current *state* and *action* by first taking a weight ($1-\\alpha$) of the old Q-value, then adding the learned value. The learned value is a combination of the reward for taking the current action in the current state, and the discounted maximum reward from the next state we will be in once we take the current action.\n",
    "\n",
    "Basically, we are learning the proper action to take in the current state by looking at the reward for the current state/action combo, and the max rewards for the next state. This will eventually cause our taxi to consider the route with the best rewards strung together."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qC-pX8P-tXLb"
   },
   "source": [
    "The Q-value of a state-action pair is the sum of the instant reward and the discounted future reward (of the resulting state). \n",
    "The way we store the Q-values for each state and action is through a **Q-table**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qC-pX8P-tXLb"
   },
   "source": [
    "##### Q-Table\n",
    "The Q-table is a matrix where we have a row for every state (500) and a column for every action (6). It's first initialized to 0, and then values are updated after training. Note that the Q-table has the same dimensions as the reward table, but it has a completely different purpose.\n",
    "\n",
    "<img src=\"assets/q-matrix-initialized-to-learned.png\" width=500px>\n",
    "\n",
    "#### Summing up the Q-Learning Process\n",
    "Breaking it down into steps, we get\n",
    "\n",
    "- Initialize the Q-table by all zeros. \n",
    "- Start exploring actions: For each state, select any one among all possible actions for the current state (S).\n",
    "- Travel to the next state (S') as a result of that action (a).\n",
    "- For all possible actions from the state (S') select the one with the highest Q-value.\n",
    "- Update Q-table values using the equation.\n",
    "- Set the next state as the current state.\n",
    "- If goal state is reached, then end and repeat the process.\n",
    "\n",
    "##### Exploiting learned values\n",
    "After enough random exploration of actions, the Q-values tend to converge serving our agent as an action-value function which it can exploit to pick the most optimal action from a given state.\n",
    "\n",
    "There's a tradeoff between exploration (choosing a random action) and exploitation (choosing actions based on already learned Q-values). We want to prevent the action from always taking the same route, and possibly overfitting, so we'll be introducing another parameter called $\\Large \\epsilon$ \"epsilon\" to cater to this during training. \n",
    "\n",
    "Instead of just selecting the best learned Q-value action, we'll sometimes favor exploring the action space further. Lower epsilon value results in episodes with more penalties (on average) which is obvious because we are exploring and making random decisions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qC-pX8P-tXLb"
   },
   "source": [
    "### Implementing Q-learning in python\n",
    "#### Training the Agent\n",
    "\n",
    "First, we'll initialize the Q-table to a $500 \\times 6$ matrix of zeros:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "q_table = np.zeros([env.observation_space.n, env.action_space.n])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NmGpm7-ytXLg"
   },
   "source": [
    "We can now create the training algorithm that will update this Q-table as the agent explores the environment over thousands of episodes.\n",
    "\n",
    "In the first part of `while not done`, we decide whether to pick a random action or to exploit the already computed Q-values. This is done simply by using the `epsilon` value and comparing it to the `random.uniform(0, 1)` function, which returns an arbitrary number between 0 and 1.\n",
    "\n",
    "We execute the chosen action in the environment to obtain the `next_state` and the `reward` from performing the action. After that, we calculate the maximum Q-value for the actions corresponding to the `next_state`, and with that, we can easily update our Q-value to the `new_q_value`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Episode: 100000\n",
      "Training finished.\n",
      "\n",
      "Wall time: 30.6 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "\"\"\"Training the agent\"\"\"\n",
    "\n",
    "import random\n",
    "from IPython.display import clear_output\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "from time import sleep\n",
    "%matplotlib inline\n",
    "\n",
    "# Hyperparameters\n",
    "alpha = 0.1\n",
    "gamma = 0.6\n",
    "epsilon = 0.1\n",
    "\n",
    "# For plotting metrics\n",
    "all_epochs = []\n",
    "all_penalties = []\n",
    "\n",
    "for i in range(1, 100001):\n",
    "    state = env.reset()\n",
    "\n",
    "    epochs, penalties, reward, = 0, 0, 0\n",
    "    done = False\n",
    "    \n",
    "    while not done:\n",
    "        if random.uniform(0, 1) < epsilon:\n",
    "            action = env.action_space.sample() # Explore action space\n",
    "        else:\n",
    "            action = np.argmax(q_table[state]) # Exploit learned values\n",
    "\n",
    "        next_state, reward, done, info = env.step(action) \n",
    "        \n",
    "        old_value = q_table[state, action]\n",
    "        next_max = np.max(q_table[next_state])\n",
    "        \n",
    "        new_value = (1 - alpha) * old_value + alpha * (reward + gamma * next_max)\n",
    "        q_table[state, action] = new_value\n",
    "\n",
    "        if reward == -10:\n",
    "            penalties += 1\n",
    "\n",
    "        state = next_state\n",
    "        epochs += 1\n",
    "        \n",
    "    if i % 100 == 0:\n",
    "        clear_output(wait=True)\n",
    "        print(f\"Episode: {i}\")\n",
    "\n",
    "print(\"Training finished.\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that the Q-table has been established over 100,000 episodes, let's see what the Q-values are at our illustration's state:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ -2.30108105,  -1.97092096,  -2.30357004,  -2.20591839,\n",
       "       -10.3607344 ,  -8.5583017 ])"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q_table[328]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The max Q-value is \"north\" (-1.971), so it looks like Q-learning has effectively learned the best action to take in our illustration's state!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qzOzAoqdtXLu"
   },
   "source": [
    "### Evaluating the agent\n",
    "Let's evaluate the performance of our agent. We don't need to explore actions any further, so now the next action is always selected using the best Q-value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Results after 100 episodes:\n",
      "Average timesteps per episode: 12.3\n",
      "Average penalties per episode: 0.0\n"
     ]
    }
   ],
   "source": [
    "\"\"\"Evaluate agent's performance after Q-learning\"\"\"\n",
    "\n",
    "total_epochs, total_penalties = 0, 0\n",
    "episodes = 100\n",
    "\n",
    "for _ in range(episodes):\n",
    "    state = env.reset()\n",
    "    epochs, penalties, reward = 0, 0, 0\n",
    "    \n",
    "    done = False\n",
    "    \n",
    "    while not done:\n",
    "        action = np.argmax(q_table[state])\n",
    "        state, reward, done, info = env.step(action)\n",
    "\n",
    "        if reward == -10:\n",
    "            penalties += 1\n",
    "\n",
    "        epochs += 1\n",
    "\n",
    "    total_penalties += penalties\n",
    "    total_epochs += epochs\n",
    "\n",
    "print(f\"Results after {episodes} episodes:\")\n",
    "print(f\"Average timesteps per episode: {total_epochs / episodes}\")\n",
    "print(f\"Average penalties per episode: {total_penalties / episodes}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "P3jqIJTltXLy"
   },
   "source": [
    "We can see from the evaluation, the agent's performance improved significantly and it incurred no penalties, which means it performed the correct pickup/dropoff actions with 100 different passengers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "P3jqIJTltXLy"
   },
   "source": [
    "#### Comparing our Q-learning agent to no Reinforcement Learning\n",
    "\n",
    "With Q-learning agent commits errors initially during exploration but once it has explored enough (seen most of the states), it can act wisely maximizing the rewards making smart moves. Let's see how much better our Q-learning solution is when compared to the agent making just random moves. \n",
    "\n",
    "We evaluate our agents according to the following metrics,\n",
    "\n",
    "- **Average number of penalties per episode:** The smaller the number, the better the performance of our agent. Ideally, we would like this metric to be zero or very close to zero.\n",
    "- **Average number of timesteps per trip:** We want a small number of timesteps per episode as well since we want our agent to take minimum steps(i.e. the shortest path) to reach the destination.\n",
    "- **Average rewards per move:** The larger the reward means the agent is doing the right thing. That's why deciding rewards is a crucial part of Reinforcement Learning. In our case, as both timesteps and penalties are negatively rewarded, a higher average reward would mean that the agent reaches the destination as fast as possible with the least penalties\"\n",
    "\n",
    "| Measure                                 \t| Random agent's performance \t| Q-learning agent's performance \t|\n",
    "|-----------------------------------------\t|--------------------------\t|--------------------------------\t|\n",
    "| Average rewards per move                \t| -3.9012092102214075      \t| 0.6962843295638126             \t|\n",
    "| Average number of penalties per episode \t| 920.45                   \t| 0.0                            \t|\n",
    "| Average number of timesteps per trip   \t| 2848.14                  \t| 12.38                          \t|                            |\n",
    "\n",
    "These metrics were computed over 100 episodes. And as the results show, our Q-learning agent nailed it!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "P3jqIJTltXLy"
   },
   "source": [
    "#### Hyperparameters and optimizations\n",
    "\n",
    "The values of `alpha`, `gamma`, and `epsilon` were mostly based on intuition and some \"hit and trial\", but there are better ways to come up with good values.\n",
    "\n",
    "Ideally, all three should decrease over time because as the agent continues to learn, it actually builds up more resilient priors;\n",
    "\n",
    "- $\\Large \\alpha$: (the learning rate) should decrease as you continue to gain a larger and larger knowledge base.\n",
    "- $\\Large \\gamma$: as you get closer and closer to the deadline, your preference for near-term reward should increase, as you won't be around long enough to get the long-term reward, which means your gamma should decrease.\n",
    "- $\\Large \\epsilon$: as we develop our strategy, we have less need of exploration and more exploitation to get more utility from our policy, so as trials increase, epsilon should decrease."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "P3jqIJTltXLy"
   },
   "source": [
    "#### Tuning the hyperparameters\n",
    "\n",
    "A simple way to programmatically come up with the best set of values of the hyperparameter is to create a comprehensive search function (similar to [grid search](https://en.wikipedia.org/wiki/Hyperparameter_optimization#Grid_search)) that selects the parameters that would result in best `reward/time_steps` ratio. The reason for `reward/time_steps` is that we want to choose parameters which enable us to get the maximum reward as fast as possible. We may want to track the number of penalties corresponding to the hyperparameter value combination as well because this can also be a deciding factor (we don't want our smart agent to violate rules at the cost of reaching faster). A more fancy way to get the right combination of hyperparameter values would be to use Genetic Algorithms.\n",
    "\n",
    "## Conclusion and What's Ahead\n",
    "\n",
    "Alright! We began with understanding Reinforcement Learning with the help of real-world analogies. We then dived into the basics of Reinforcement Learning and framed a Self-driving cab as a Reinforcement Learning problem. We then used OpenAI's Gym in python to provide us with a related environment, where we can develop our agent and evaluate it. Then we observed how terrible our agent was without using any algorithm to play the game, so we went ahead to implement the Q-learning algorithm from scratch. The agent's performance improved significantly after Q-learning. Finally, we discussed better approaches for deciding the hyperparameters for our algorithm.\n",
    "\n",
    "Q-learning is one of the easiest Reinforcement Learning algorithms. The problem with Q-earning however is, once the number of states in the environment are very high, it becomes difficult to implement them with Q table as the size would become very, very large. State of the art techniques uses Deep neural networks instead of the Q-table (Deep Reinforcement Learning). The neural network takes in state information and actions to the input layer and learns to output the right action over the time. Deep learning techniques (like Convolutional Neural Networks) are also used to interpret the pixels on the screen and extract information out of the game (like scores), and then letting the agent control the game.\n",
    "\n",
    "We have discussed a lot about Reinforcement Learning and games. But Reinforcement learning is not just limited to games. It is used for managing stock portfolios and finances, for making humanoid robots, for manufacturing and inventory management, to develop general AI agents, which are agents that can perform multiple things with a single algorithm, like  the same agent playing multiple Atari games. Open AI also has a platform called universe for measuring and training an AI's general intelligence across myriads of games, websites and other general applications."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab": {
     "autoexec": {
      "startup": false,
      "wait_interval": 0
     }
    },
    "colab_type": "code",
    "id": "FOxsJuSFHuMS"
   },
   "source": [
    "## Now, to you\n",
    "If you'd like to continue with this project to make it better, here's a few things you can add:\n",
    "- Turn this code into a module of functions that can use multiple environments\n",
    "- Tune alpha, gamma, and/or epsilon using a decay over episodes\n",
    "- Implement a grid search to discover the best hyperparameters\n",
    "\n",
    "Shoot us a tweet @learndatasci with a repo or gist and we'll check out your additions!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "default_view": {},
   "name": "A practical introduction to Reinforcement Learning.ipynb",
   "provenance": [],
   "version": "0.3.2",
   "views": {}
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
